package QuickSort;

public class QuickSort {

    //找中间大小的值的 下标
    private static int findMidIndex(int[] array, int start, int end){
        //mindIndex : 中间坐标
        int midIndex = (start + end) / 2;

        //先比首尾两个值的大小
        if(array[start] < array[end]) {
            if(array[midIndex] < array[start]) return start;
            else if(array[midIndex] > array[end]) return end;
            else return midIndex;
        }else {
            if (array[midIndex] >array[start]) return start;
            else if(array[midIndex] < array[end]) return end;
            else return midIndex;
        }
    }

    //  挖坑快排 保证一个数有序
    private static int partition (int[] array, int left, int right){
        int pivot = array[left];
        while(left < right){
            //找右边的小值

            //为啥要 = 防止首尾两个数相同
            while(left < right && array[right] >= pivot) right--;
            //交换, 默认最开始 左边那个为坑
            array[left] = array[right];

            //找左边的大值
            while(left < right && array[left] <= pivot) left++;
            array[right] = array[left];
        }
        //相遇
        array[left] = pivot;
        return left;
    }
    private static void swap(int[] array, int start, int end){
        int tmp = array[start];
        array[start] = array[end];
        array[end] = tmp;
    }
    public static void quick(int[] array, int start, int end){
        //防止没有 数组有序 没有左树或者右树的情况
        if(start >= end) return;

        //三数中间数
        int index = findMidIndex(array, start, end);
        swap(array, start, index);

        int pivot = partition(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }


}
